CF757E Bash Plays with Functions

根据题意进行分类讨论:

τ(n)\tau(n)nn 的不同质因数的个数。

  1. r=0r=0

因为要求 gcd(p,q)=1\gcd(p,q)=1 , 那么相同的质因数只会全部在 ppqq 中。

每种不同的质因数有 22 种选法,那么 f0(n)=2τ(n)f_0(n)=2^{\tau(n)}

可以看出,f0(n)f_0(n) 是一个积性函数。

  1. r=0r\not =0

fr(n)=u×v=nfr1(u)+fr1(v)2f_r(n)=\sum_{u \times v=n} \frac{f_{r-1}(u)+f_{r-1}(v)}{2}

fr(n)=unfr1(u)+fr1(nu)2f_r(n)=\sum_{u|n} \frac{f_{r-1}(u)+f_{r-1}(\frac{n}{u})}{2}

fr(n)=unfr1(u)f_r(n)=\sum_{u|n} f_{r-1}(u)

这是一个迪利克雷卷积的形式: fr=fr11f_r =f_{r-1} * 1

因为 f0(n)f_0(n) 是一个积性函数,那么 fr(n)f_r(n) 也是一个积性函数,只需要求出质数的幂的函数值即可。

fr(pw)=dpwfr1(d)f_r(p^w)=\sum_{d|p^w} f_{r-1}(d)

fr(pw)=d=0wfr1(pd)f_r(p^w)=\sum_{d=0}^w f_{r-1}(p^d)

fr(pw)=fr(pw1)+fr1(pw)f_r(p^w)=f_{r}(p^{w-1}) +f_{r-1}(p^w)

递推求解就可以了。

所以为什么其他题解都用了前缀和啊

#include <cstdio>

const int MAXN = 1e6 , LOG = 20 , Mod = 1e9 + 7;

int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < Mod ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }

int prnum , prime[ MAXN + 5 ] , low[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	low[ 1 ] = 1; vis[ 1 ] = 0;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) prime[ ++ prnum ] = i , low[ i ] = i;
		for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1; low[ i * prime[ j ] ] = prime[ j ];
			if( i % prime[ j ] == 0 ) break;
		}
	}
}

int f[ MAXN + 5 ][ LOG + 1 ];
void Init( ) {
	f[ 0 ][ 0 ] = 1; //f0(1)=1
	for( int i = 1 ; i <= LOG ; i ++ ) f[ 0 ][ i ] = 2; //f0(p^k)=2
	for( int i = 1 ; i <= MAXN ; i ++ ) {
		f[ i ][ 0 ] = f[ i - 1 ][ 0 ];
		for( int j = 1 ; j <= LOG ; j ++ )
			f[ i ][ j ] = Add( f[ i ][ j ] , Add( f[ i ][ j - 1 ] , f[ i - 1 ][ j ] ) );
	}
}

int T , r , n;
int main( ) {
	sieve(); Init();
	scanf("%d",&T);
	while( T -- ) {
		scanf("%d %d",&r,&n);
		int Ans = 1;
		while( n != 1 ) {
			int p = low[ n ] , w = 0;
			for( ; n % p == 0 ; n /= p , w ++ );
			Ans = Mul( Ans , f[ r ][ w ] );
		}
		printf("%d\n", Ans );
	}
	return 0;
}